package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 1008. 先序遍历构造二叉树
 * @author feizns
 * @since 2020/3/10
 */
public class BstFromPreorder {

    public static void main(String[] args) {
        final TreeNode node = bstFromPreorder(new int[]{8, 5, 1, 7, 10, 12});
        System.out.println(node);
    }

    public static TreeNode bstFromPreorder(int[] preOrder) {
        return buildTree(preOrder, 0, preOrder.length - 1);
    }

    private static TreeNode buildTree(int[] preOrder, int l, int r) {
        TreeNode ret = null;
        if ( l == r )
            ret = new TreeNode(preOrder[l]);
        else if ( l < r ) {
            ret = new TreeNode(preOrder[l]);
            int i = l + 1;
            while ( i <= r && preOrder[i] < ret.val ) {
                i++;
            }
            ret.left = buildTree(preOrder, l + 1, i - 1);
            ret.right = buildTree(preOrder, i, r);
        }
        return ret;
    }

}
